package LeetCode;

import java.awt.*;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.TreeSet;

public class LC_480_SlidingWindowMedian {

    public static void main(String[] args) {

    }

    public class Solution {

        public double[] medianSlidingWindow(int[] nums, int k) {
            int n = nums.length;
            int m = n - k + 1; // 结果的尺寸
            double[] res = new double[m];
            //两个堆，一个最大堆，一个最小
            PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, Collections.reverseOrder());
            PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
            for (int i = 0; i < n; i++) {
                int num = nums[i];
                // 让maxHeap始终保存小于一半的值，minHeap保存大于一半的，正好两半
                if (maxHeap.size() == 0 || maxHeap.peek() >= num)
                    maxHeap.add(num);
                else minHeap.add(num);
                // 维护两个堆，保证两个堆得大小，要么保持一致（偶数时），要么maxHeap多一个（奇数时）
                if (minHeap.size() > maxHeap.size())
                    maxHeap.add(minHeap.poll());
                if (maxHeap.size() > minHeap.size() + 1)
                    minHeap.add(maxHeap.poll());
                // 如果需要输出
                if (i - k + 1 >= 0) {
                    if (k % 2 == 1)
                        res[i - k + 1] = maxHeap.peek();
                    else
                        res[i - k + 1] = (maxHeap.peek() / 2.0 + minHeap.peek() / 2.0); // 小心溢出
                    //移除并更新
                    int toBeRemove = nums[i - k + 1];
                    if (toBeRemove <= maxHeap.peek())
                        maxHeap.remove(toBeRemove);
                    else minHeap.remove(toBeRemove);
                    // 维护两个堆，保证两个堆得大小，要么保持一致（偶数时），要么maxHeap多一个（奇数时）
                    if (minHeap.size() > maxHeap.size())
                        maxHeap.add(minHeap.poll());
                    if (maxHeap.size() > minHeap.size() + 1)
                        minHeap.add(maxHeap.poll());
                }
            }
            return res;
        }

    }

    public class Solution_2 {
        private Comparator<Point> cmp = (a, b) -> {
            if (a.getX() != b.getX())
                return Double.compare(b.getX(), a.getX());
            return Double.compare(b.getY(), a.getY());
        };

        private TreeSet<Point> hiSet = new TreeSet<>(cmp);
        private TreeSet<Point> loSet = new TreeSet<>(cmp);

        private double getMedian() {
            if (hiSet.size() > loSet.size()) return hiSet.last().getX();
            return ((hiSet.last().getX()) + (loSet.first().getX())) / 2;
        }

        private void addValue(int val, int i) {
            Point p = new Point(val, i);
            if (hiSet.isEmpty() || hiSet.last().getX() < p.getX())
                hiSet.add(p);
            else
                loSet.add(p);
            adjustSet();
        }

        private void removeValue(int val, int i) {
            Point p = new Point(val, i);
            if (hiSet.contains(p)) hiSet.remove(p);
            else loSet.remove(p);
            adjustSet();
        }

        private void adjustSet() {
            if (loSet.size() > hiSet.size())
                hiSet.add(loSet.pollFirst());
            else if (hiSet.size() > loSet.size() + 1)
                loSet.add(hiSet.pollLast());
        }

        public double[] medianSlidingWindow(int[] nums, int k) {
            double[] ans = new double[nums.length - k + 1];
            for (int i = 0; i < nums.length; i++) {
                if (i >= k) removeValue(nums[i - k], i - k);
                addValue(nums[i], i);
                if (i >= k - 1) ans[i - k + 1] = getMedian();
            }
            return ans;
        }

    }
}